Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра ЕОМ
КУРСОВА РОБОТА з дисципліни: «Паралельні та розподілені обчислення» на тему: «Паралельне виконання операцій множення матриць» Львів – 2013 Завдання Розробити схему та описати процедуру перемноження матриці А (розмірністю N1*N2) на матрицю В (розмірністю N2*N3) на структурі з восьми процесорів. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  С о п у ш И н с ь к и й М и к о л а Б о   3 1  4 2    5 8 8 6 7   7      N1 = 2Б = 240, N2 = 4П = 296, N3 = 2I =349 Таблиця 1. Часові параметри Співвідношення часових параметрів Пояснення  tu = tw час виконання однієї операції множення  ts = 1/10 * tw час виконання однієї операції сумування  tp = 1/8 * tw час виконання однієї операції пересилання даних між процесорами  tz = 1/7 * tw час виконання операції завантаження одних даних  tW час виконання операції вивантаження одних даних   Таблиця 2. Кодування букв 3 6 2 5 10 13 14(17 11(12  п и о Ш к м л й  219 91 250 157 47 43 212 146  DB 5B FA 9D 2F 2B D4 92   Таблиця 3. Матриця суміжності 1 2 3 4 5 6 7 8  1 0 1 0 1 1 0 1 1  2 0 0 0 1 1 0 1 1  3 1 1 0 1 1 0 1 0  4 1 0 0 0 1 1 0 1  5 0 0 1 0 0 1 1 1  6 0 0 1 0 1 0 1 1  7 1 1 0 1 0 1 0 0  8 1 0 0 1 0 0 1 0   z = 0909760 (номер залікової книжки) Type = (
i) mod 3 + 1 = (0 + 9 + 0 + 9 + 7 + 6 + 0) mod 3 = 31 mod 3 = 1 Type = 1 спільна пам’ять. Анотація В даній курсовій роботі розроблено алгоритм паралельного перемноження матриць на структурі з восьми процесорів. Завантаження даних відбувається з спільної пам’яті. Вхідні матриці мають розмірності А(240*296) та В(296*349). Робота складається з розрахунку часових характеристик алгоритму, розробки функціональної схеми алгоритму та програмної реалізації. Відповідно до часових затрат паралельного алгоритму визначено його ефективність відносно послідовного. Програмно, алгоритм реалізований на Java з консольним інтерфейсом. Паралелізація досягнута за допомогою потоків.  Зміст Вступ 5 1. Теоретичний розділ 6 2. Розробка функціональної схеми 9 4. Розрахунковий розділ 12 5. Розробка програми 14 Висновки 17 Література 18  Вступ Паралельні обчислювальні системи - комп'ютерні системи, що реалізовують тим або іншим способом паралельну обробку даних на багатьох обчислювальних вузлах для підвищення загальної швидкості розрахунку. Ідея розпаралелення обчислень базується на тому, що більшість завдань можуть бути розділені на набір менших завдань, які можуть бути вирішені одночасно. Зазвичай паралельні обчислення вимагають координації дій. Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора має фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму. Розподілені обчислення - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу. Розподілені обчислення є окремим випадком паралельних обчислень, тобто одночасного розв'язання різних частин одного обчислювального завдання декількома процесорами одного або кількох комп'ютерів. Тому нео...